<?php

class GoodsObject {
    var $name;
    var $price;
}

class OrderSplit {
    var $max_limit = 5000;
    var $base_count = 4;
    var $fanyan_count = 26;
    var $bianyi = 10;

    function __construct($data) {
        $this->source = array();
        //保存基础数据
        foreach ($data as $key => &$item) {
            $i = $item['num'];
            while ($i--) {
                $ins = new GoodsObject();
                $ins->name = $item['name'];
                $ins->price = $item['price'];
                $this->source[] = $ins;
            }
        }


    }

    function split() {
        $result = array();

        //所有单价超过5000的，不参与运算
        $_result = array();
        foreach ($this->source as $key => $val) {
            if ($val->price >= 5000) {
                $_result[] = $val;
                unset($this->source[$key]);
            }
        }
        if (count($_result)) {
            $result[] = $_result;
        }

        while (true) {
            $total = 0;
            foreach ($this->source as $value) {
                $total += $value->price;
            }
            if ($total < $this->max_limit) {
                break;
            }

            $this->base_group();

            $this->start_fanyan();

            //取出一个可行解
            if ($_result = $this->get_one_result()) {
                $result[] = $_result;
            }

        }

        if (count($this->source)) {
            $result[] = $this->source;
        }


        return $result;
    }

    function get_one_result() {
        $new_arr = $this->arraySort($this->groups, 'shiyingdu');
        $_result = array_pop($new_arr);
        $temp = array();
        foreach ($_result['value'] as $key => $val) {
            if ($val == 1) {
                $temp[] = $this->source[$key];
                $this->source[$key] = null;
            }
        }
        $new = array();
        foreach ($this->source as $key => $val) {
            if ($val != null) {
                $new[] = $val;
            }
        }
        $this->source = $new;
        return $temp;

    }

    /**
     * @desc arraySort php二维数组排序 按照指定的key 对数组进行排序
     * @param array $arr 将要排序的数组
     * @param string $keys 指定排序的key
     * @param string $type 排序类型 asc | desc
     * @return array
     */
    function arraySort($arr, $keys, $type = 'asc') {
        $keysvalue = $new_array = array();
        foreach ($arr as $k => $v) {
            $keysvalue[$k] = $v[$keys];
        }
        $type == 'asc' ? asort($keysvalue) : arsort($keysvalue);
        reset($keysvalue);
        foreach ($keysvalue as $k => $v) {
            $new_array[$k] = $arr[$k];
        }
        return $new_array;
    }

    function tubian($arr) {
        if (rand(0, 100) < $this->bianyi) {
            $index = rand(0, count($arr['value']) - 1);
            if ($arr['value'][$index] == 1) {
                $arr['value'][$index] = 0;
            } else {
                $arr['value'][$index] = 1;
            }
            $arr['shiyingdu'] = $this->get_shiyingdu($arr['value']);
        }
        return $arr;
    }


    function youxuan($arr) {
        $new_arr = $this->arraySort($arr, 'shiyingdu');
        return array(array_pop($new_arr), array_pop($new_arr));
    }

    function randomFloat($min = 0, $max = 1) {
        return $min + mt_rand() / mt_getrandmax() * ($max - $min);
    }

    function taotai() {
//        $new_arr = $this->arraySort($this->groups, 'shiyingdu');
        $total = 0;
        foreach ($this->groups as $key => $val) {
            $total += $val['shiyingdu'];
        }
        //整个种群全部淘汰
        if ($total == 0) {
            return false;
        }
        $rate = array();
        foreach ($this->groups as $key => $val) {
            $rate[] = $val['shiyingdu'] / $total;
        }
        $base = 0;
        foreach ($rate as $key => $val) {
            $rate[$key] = $base;
            $base += $val;
        }

        $random = $this->randomFloat();

        $count = count($rate);
        while ($count--) {
            if ($random > $rate[$count]) {
                unset($this->groups[$count]);
                break;
            }
        }

    }

    function cal_shiyingdu($arr) {
        $shiyingdu = array();
        foreach ($arr as $xulie) {
            $shiyingdu[] = array(
                'shiyingdu' => $this->get_shiyingdu($xulie),
                'value' => $xulie
            );
        }
        return $shiyingdu;
    }

    function start_fanyan() {
        for ($i = 0; $i < $this->fanyan_count; $i++) {
            //得到父亲
            list($father, $mother) = $this->youxuan($this->groups);
            list($child1, $child2) = $this->make_children($father, $mother);

            $child1 = $this->tubian($child1);
            $child2 = $this->tubian($child2);

            $this->groups[] = $child1;
            $this->groups[] = $child2;
            //排除掉适应度最低的两个
            if($this->taotai() === false){
                $this->base_group();
                $this->start_fanyan();
                return false;
            }
            if ($this->taotai() === false) {
                $this->base_group();
                $this->start_fanyan();
                return false;
            }

        }


    }

    function get_shiyingdu($xulie) {
        if ($this->need_kill($xulie) === true) {
            return 0;
        }
        return $this->need_kill($xulie);
    }

    function base_group() {
        $this->groups = array();
        for ($j = 0; $j < $this->base_count; $j++) {
            $item = array();
            $max = 0;

            //至少给出一半有解的情况
            if ($j < $this->base_count / 2) {

                $index = rand(0, count($this->source) - 1);
                for ($i = 0; $i < $index; $i++) {
                    $item[] = 0;
                }
                for ($i = $index; $i < count($this->source); $i++) {
                    $max += $this->source[$i]->price;
                    if ($max < $this->max_limit) {
                        $item[] = 1;
                    } else {
                        $item[] = 0;
                    }
                }
            } else {
                for ($i = 0; $i < count($this->source); $i++) {
                    if (rand(0, 1) == 1) {
                        $item[] = 1;
                    } else {
                        $item[] = 0;
                    }
                }
            }

            $this->groups[] = $item;
        }
        $this->groups = $this->cal_shiyingdu($this->groups);
    }

    function make_children($father, $mother) {
        $index = rand(0, count($father['value']) - 1);
        $swap = null;
        for ($i = $index; $i < count($father['value']); $i++) {
            $swap = $father['value'][$i];
            $father['value'][$i] = $mother['value'][$i];
            $mother['value'][$i] = $swap;
        }
        $father['shiyingdu'] = $this->get_shiyingdu($father['value']);
        $mother['shiyingdu'] = $this->get_shiyingdu($mother['value']);
        return array($father, $mother);
    }

    function need_kill($xulie) {
        $max = 0;
        foreach ($xulie as $key => $val) {
            if ($val == 1) {
                $max += $this->source[$key]->price;
            }
        }
        if ($max > $this->max_limit) {
            return true;
        }

        return $max;
    }


}


$test = array(
    array(
        'num' => 10,
        'price' => 100
    ),
    array(
        'num' => 20,
        'price' => 200
    ),
    array(
        'num' => 30,
        'price' => 450
    ),
    array(
        'num' => 5,
        'price' => 2500
    )
);
//$a = new OrderSplit($test);
//$a->split();

?>
<!doctype html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>Document</title>
    <script src="/data/resource/js/jquery.js"></script>
    <style>
        div, p {
            overflow: hidden;
        }

        input {
            width: 20%;
            float: left;
            display: block;
            margin-right: 2%;

        }
    </style>
</head>
<body>
<?php
if ($_POST) {
    $arr = array();
    foreach ($_POST['name'] as $key => $val) {
        if (empty($val)) {
            continue;
        }
        $arr[] = array(
            'name' => $val,
            'price' => $_POST['price'][$key],
            'num' => $_POST['num'][$key],
        );
    }

    $ins = new OrderSplit($arr);
    $result = $ins->split();

    $_arr = array();
    foreach ($result as $value) {
        $arr = array();
        foreach ($value as $item) {
            if (!isset($arr[$item->name])) {
                $arr[$item->name] = array('price' => $item->price, 'num' => 0);
            }
            $arr[$item->name]['num']++;
        }
        $_arr[] = $arr;
    }
    $arr = $_arr;
    foreach ($arr as $key => $item) {
        ?>
        <div>
            <p>订单<?php echo(++$key); ?></p>
            <ul>
                <?php
                $total = 0;
                foreach ($item as $name => $i) {
                    $total += $i['price'] * $i['num'];
                    ?>
                    <li style="border-bottom:1px dashed #ddd;">
                        <p>
                            商品名：<?php echo $name; ?>
                        </p>

                        <p>
                            商品价格：<?php echo $i['price']; ?>
                        </p>

                        <p>
                            商品数量：<?php echo $i['num'] ?>
                        </p>
                    </li>
                    <?php
                }
                ?>
                <li>
                    <?php
                    echo "订单总价 ：" . $total;
                    ?>
                </li>
            </ul>
        </div>
        <?php
    }

}
?>
<div class="model" style="display: none;">
    <p>
        <input type="text" name="name[]" placeholder="商品名(不填视为没有该商品)">
        <input type="text" name="price[]" placeholder="商品价格(加上税的）">
        <input type="number" name="num[]" placeholder="商品数量">
    </p>
</div>
<form action="chaifen.php" method="post">
    <div class="box">

    </div>
    <p>
        <button class="button add" type="button">增加</button>
        <button class="submit" type="submit">提交拆单</button>
    </p>
</form>
</body>
</html>
<script>
    $('.add').click(function () {
        $('.box').append($('.model').html())
    }).trigger('click');
</script>